package hl.leco.greedy;

import java.util.*;

/**
 * 
 * @author Liu Huan
 */

/**
 * 贪心策略：从问题出发，最大团队表现力
 */
public class MaxTeamPerformance {
	
	public static void main(String[] args) {
		/**
		 * 输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
		 * 输出：60
		 * 解释：
		 * 我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。
		 * 他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
		 * 
		 * 6
		 * [2,10,3,1,5,8]
		 * [5,4,3,9,7,2]
		 * 3
		 */
		int[] speed = {2,10,3,1,5,8};
		int[] efficiency = {5,4,3,9,7,2};
		System.out.println("最大团队表现力：" + maxPerformance(6, speed, efficiency, 3));
	}
	
	public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
		System.out.println("将 speed 和 efficiency 整合成一张二维表:");
		int[][] items = new int[n][2];
		for (int i = 0; i < n; i++) {
			items[i][0] = speed[i];
			items[i][1] = efficiency[i];
		}
//		for (int i = 0; i < n; i++) {
//			System.out.println(items[i][0] + "\t" + items[i][1]);
//		}
		
		System.out.println("按照 efficiency 项从大到小排序:");
		Arrays.sort(items, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1] - o1[1];
			}
		});
//		for (int i = 0; i < n; i++) {
//			System.out.println(items[i][0] + "\t" + items[i][1]);
//		}
		
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		long res = 0, sum = 0;
		for(int i = 0 ; i < n ; i++){// 枚举 n 次最小效率，找到每次 右边 最多 k-1 个的最大速度和，（使用 优先队列 poll 出最小值）
//			int effitem = items[i][1];
//			for (int j = 0; j < i; j++) {
//				queue.offer(items[j][0]);
//			}
//			while (queue.size() > k-1) {
//				queue.poll();
//			}
//			int len = queue.size();
//			for (int j = 0; j < len; j++) {
//				sum += queue.poll();
//			}
//			res = Math.max(res, (sum + items[i][0]) * effitem);
//			sum = 0;
//			queue.clear();
			
			if(queue.size() > k - 1){
				sum -= queue.poll();
			}
			res = Math.max(res, (sum + items[i][0])* items[i][1]);
			queue.add(items[i][0]);
			sum += items[i][0];
		}
		return (int)(res % ((int)1e9 + 7));
	}
	
}
